package LeetCodeSection;/*
 *
 *@author:    Xavier
 *@data:      2023 - 08 - 20
 *@time:      14:31
 *
 */


//9. 从前序与中序遍历序列构造二叉树
//https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
public class Pre_In_OrderStructureBinaryTree {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

    class Solution {
        public int preIndex = 0;
        public TreeNode buildTree(int[] preorder, int[] inorder) {
            return buildTreeChild(preorder, inorder, 0, inorder.length-1);
        }

        public TreeNode buildTreeChild(int[] preorder, int[] inorder, int inBegin, int inEnd) {
            //递归的出口
            if (inBegin > inEnd) {
                return null;
            }


            //创建根节点
            TreeNode root = new TreeNode(preorder[preIndex]);
            //根据前序 找到 中序中的根
            int rootIndex = rootFind(inorder, inBegin, inEnd, preorder[preIndex]);
            //前序的根继续走。 寻找中序的根
            preIndex++;
            //先走左 创建左节点 然后右 前序遍历：根->左->右
            root.left = buildTreeChild(preorder, inorder, inBegin, rootIndex-1);
            root.right = buildTreeChild(preorder, inorder, rootIndex+1, inEnd);

            return root;
        }

        //根据前序遍历 在中序遍历中找到 中序的 根节点 返回下标
        public int rootFind(int[] inorder, int inBegin, int inEnd, int key) {
            for (int i = inBegin; i <= inEnd; i++) {
                if (inorder[i] == key) {
                    return i;
                }
            }
            return -1;
        }
    }


}
